package com.learning;

import Entry.ListNode;
import Entry.TreeNode;

import java.math.BigInteger;
import java.util.*;

public class Middle {
    /**
     * 18四数之和
     * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int len=nums.length;
        if(len<4) return new ArrayList<List<Integer>>();
        Set<List<Integer>> list=new HashSet<>();
        for(int i=0;i<len-3;i++){
            for(int j=i+1;j<len-2;j++){
                int l=j+1,r=len-1;
                while (l<r){
                    int t=nums[i]+nums[j]+nums[l]+nums[r];
                    if(t<target){
                        l++;
                    }else if(t>target){
                        r--;
                    }else {
                        List<Integer> node=new ArrayList<>();
                        node.add(nums[i]);node.add(nums[j]);node.add(nums[l]);node.add(nums[r]);
                        list.add(node);
                        l++;r--;
                     }
                }
            }
        }
        return new ArrayList<>(list);
    }

    public ListNode swapPairs(ListNode head) {
        if(head==null) return head;
        ListNode p=head,pnext=p.next,pre=head;int n=0;
        if(pnext!=null){
                p.next=pnext.next;
                pnext.next=p;
                head=pnext;
                n++;
        }
        if(pnext!=null&&p.next!=null){
                pre=p;
                p=p.next;
                pnext=p.next;n++;
        }
       while (pnext!=null&&p.next!=null){
            if(n%2==0){
                p.next=pnext.next;
                pnext.next=p;
                pre.next=pnext;
            }else {
                pre=p;
                p=p.next;
                pnext=p.next;
            }
            n++;
        }
        return head;
    }

    /**
     * 89格雷编码
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {

        List<Integer> list=new ArrayList<>();
        if(n<0)return list;
        else if(n==0) {
            list.add(0);
            return list;
        }else if(n==1){
            list.add(0);
            list.add(1);
            return list;
        }else {
            int len=(int)Math.pow(2,n);
            int[]data=new int[len];
            data[0]=0;data[1]=1;
            for(int i=1;i<n;i++){
                int temp=(int)Math.pow(2,i);
                for(int j=0;j<temp;j++){
                    data[temp+j]=temp+data[temp-j-1];
                }
            }
            for(int i=0;i<len;i++){
                list.add(data[i]);
            }
            return list;
        }
    }
    /**
     * 6
     * Z字形变换
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if(numRows==1)
            return s;
        char[]cs=s.toCharArray();
        int len=cs.length;
        String [] result=new String[numRows];
        for(int i=0;i<numRows;i++){
            result[i]="";
        }
        for(int i=0;i<len;i++){
            int mod=i%(2*numRows-2);
            if(mod<numRows){
                result[mod]+=cs[i];
            }else {
                result[2*numRows-2-mod]+=cs[i];
            }
        }
        String res="";
        for(int i=0;i<numRows;i++){
            res+=result[i];
        }
        return res;
    }

    /**
     * 64最小路径和
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int H=grid.length;
        int W=grid[0].length;
        int data[][]=new int[H][W];
        data[0][0]=grid[0][0];
        for (int i=0;i<H;i++){
            for (int j=0;j<W;j++){
                if(i==0&&j==0)continue;
                int left=Integer.MAX_VALUE,up=Integer.MAX_VALUE;
                if(j-1>=0)left=data[i][j-1];
                if(i-1>=0) up=data[i-1][j];
                int min=left<up?left:up;
                data[i][j]=min+grid[i][j];
            }
        }
        return data[H-1][W-1];
    }

    /**12
     * 整数转罗马数字
     * @param num
     * @return
     */
    public String intToRoman(int num) {
        String sb="";
        int n=num/1000;
        if(n==0){

        }else{
            for(int i=0;i<n;i++){
                sb+="M";
            }
        }
        num=num%1000;
        n=num/100;
        if(n==0){

        }else if(n==4){
            sb+="CD";
        }else if(n==9){
            sb+="CM";
        }else {
            if(n>=5){
                sb+="D";
                n=n-5;
            }
            for (int i=0;i<n;i++){
                sb+="C";
            }
        }
        num=num%100;
        n=num/10;
        if(n==0){

        }else if(n==4){
            sb+="XL";
        }else if(n==9){
            sb+="XC";
        }else {
            if(n>=5){
                sb+="L";
                n=n-5;
            }
            for (int i=0;i<n;i++){
                sb+="X";
            }
        }
        num=num%10;
        n=num/1;
        if(n==0){

        }else if(n==4){
            sb+="IV";
        }else if(n==9){
            sb+="IX";
        }else {
            if(n>=5){
                sb+="V";
                n=n-5;
            }
            for (int i=0;i<n;i++){
                sb+="I";
            }
        }
        return sb;
    }

    /**
     * 11盛最多水的容器
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int area=0;
        int len=height.length;
        for (int i=0;i<len-1;i++){
            for (int j=i+1;j<len;j++){
                int min=height[i]<height[j]?height[i]:height[j];
                int temp=min*(j-i);
                area=area>temp?area:temp;
            }
        }
        return area;
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> node=new ArrayList<>();
        combinationOneSum(candidates,target,list,node,0);
        return list;
    }
    private void combinationOneSum(int[] candidates, int target, List<List<Integer>> list, List<Integer> node, int index) {
        if(target==0){
            list.add(new ArrayList<>(node));
            return;
        }
        if(target<0){
            return;
        }
        for(int i=index;i<candidates.length;i++){
            node.add(candidates[i]);
            combinationOneSum(candidates, target-candidates[i], list, node, i);
            node.remove(node.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> node=new ArrayList<>();
        combinationOneSum2(candidates,target,list,node,0);
        return list;
    }
    private void combinationOneSum2(int[] candidates, int target, List<List<Integer>> list, List<Integer> node, int index) {
        if(target==0){
            List<Integer> temp=new ArrayList<>(node);
            if(list.contains(temp))return;
            list.add(new ArrayList<>(node));
            return;
        }
        if(target<0){
            return;
        }
        for(int i=index;i<candidates.length;i++){
            node.add(candidates[i]);
            combinationOneSum2(candidates, target-candidates[i], list, node, i+1);
            node.remove(node.size()-1);
        }
    }


    public String multiply(String num1, String num2)
    {
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }
        else {
            int len1=num1.length(),len2=num2.length();
            if(len1==0||len2==0){
                return "";
            }
            int []data=new int[len1+len2];
            for(int i=len1-1;i>=0;i--){
                int add=0;
                for(int j=len2-1;j>=0;j--){
                    int mul=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                    int sum=data[i+j+1]+add+mul%10;
                    data[i+j+1]=sum%10;
                    add=mul/10+sum/10;
                }
                data[i]+=add;
            }
            int i=0;
            while (i<data.length){
                if(data[i]==0){i++;continue;}
                else {
                    break;
                }
            }
            StringBuilder sb=new StringBuilder();
            for(;i<data.length;i++){
                sb.append(data[i]);
            }
            return sb.toString();
        }

    }

    public String simplifyPath(String path) {
        String []data=path.split("/");
        int len=data.length;
        Stack<String> stack=new Stack<>();
        for(int i=0;i<len;i++){
            String s=data[i];
            if(s.equals("")||s.equals(".")){
                continue;
            }else if(s.equals("..")){
                if(!stack.empty()){
                    stack.pop();
                }
            }else {
                stack.push(s);
            }
        }
        if(stack.empty()) return "/";
        StringBuilder sb=new StringBuilder();
        while (!stack.empty()){
            sb.insert(0,stack.pop());
            sb.insert(0,"/");
        }
        return sb.toString();
    }

    public String getPermutation(int n, int k) {
        int []dp=new int[n];
        dp[0]=1;
        for(int i=1;i<n;i++){
            dp[i]=dp[i-1]*i;
        }
        StringBuilder sb=new StringBuilder();
        --k;
        StringBuilder s=new StringBuilder("123456789");
        for(int i=n;i>0;i--){
            int temp=dp[i-1];
            int mod=k/temp;
            k=k%temp;
            sb.append(s.charAt(mod));
            s.deleteCharAt(mod);
        }
        return sb.toString();
    }

    public int removeDuplicates(int[] nums) {
        int len=nums.length;
        int left=0,right=1;
        while (right<nums.length){
            while (nums[left]==nums[right]&&right<nums.length&&right-left<2){
                right++;
            }
            while (nums[left]==nums[right]&&right<nums.length){
                nums[right]=nums[right+1];
                len--;
            }
            left=right;
            right++;
        }
        return len;
    }

    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> res=new ArrayList<>();
        if(N%2==0){
            return res;
        }else if(N==1){
            res.add(new TreeNode(0));
            return res;
        }else {
            for(int i=1;i<N;i=i+2){
                if(N-i-1<1)continue;
                List<TreeNode> left=allPossibleFBT(i);
                List<TreeNode> right=allPossibleFBT(N-1-i);
                for (TreeNode l:left) {
                    for(TreeNode r:right){
                        TreeNode root=new TreeNode(0);
                        root.left=l;
                        root.right=r;
                        res.add(root);
                    }
                }
            }
            return res;
        }
    }
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        int len = pre.length;
        if (len == 0) {
            return null;
        } else {
            int num = pre[0];
            TreeNode root = new TreeNode(num);
            int i = 0;
            for (; i < len; i++) {
                if (post[i] == num) break;
            }
            int beforelen = i;
            int[] bp = new int[beforelen];
            int[] bi = new int[beforelen];
            for (int a = 0; a < beforelen; a++) {
                bp[a] = pre[a + 1];
                bi[a] = post[a];
            }
            root.left = constructFromPrePost(bp, bi);
            int[] ap = new int[len - beforelen - 1];
            int[] ai = new int[len - beforelen - 1];
            for (int a = beforelen + 1; a < len; a++) {
                ap[a - beforelen - 1] = pre[a];
                ai[a - beforelen - 1] = post[a];
            }
            root.right = constructFromPrePost(ap, ai);
            return root;
        }
    }


    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int len1=grid.length,len2=grid[0].length;
        int dx[]=new int[len2];
        int dy[]=new int[len1];
        for(int j=0;j<len2;j++){
            int max=0;
            for(int i=0;i<len1;i++){
                max=max>grid[i][j]?max:grid[i][j];
            }
            dx[j]=max;
        }
        for(int i=0;i<len1;i++){
            int max=0;
            for(int j=0;j<len2;j++){
                max=max>grid[i][j]?max:grid[i][j];
            }
            dy[i]=max;
        }
        int sum=0;
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                int min=dx[j]<dy[i]?dx[j]:dy[i];
                sum+=min-grid[i][j];
            }
        }

        return sum;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTreePart(nums,0,nums.length-1);
    }

    private TreeNode constructMaximumBinaryTreePart(int[] nums, int start, int end) {
        if(end-start<0){
            return null;
        }
        int max=Integer.MIN_VALUE;
        int index=-1;
        for(int i=start;i<=end;i++){
            if(nums[i]>max){
                max=nums[i];
                index=i;
            }
        }
        TreeNode root=new TreeNode(nums[index]);
        root.left=constructMaximumBinaryTreePart(nums,start,index-1);
        root.right=constructMaximumBinaryTreePart(nums,index+1,end);
        return root;

    }

    public int[] countBits(int num) {
        int []res=new int[num+1];
        res[0]=0;
        if(num<=0) return res;
        res[1]=1;
        int index=1;
        int temp=(int)Math.pow(2,index);
        for(int i=2;i<=num;i++){
            res[i]=res[i-temp]+1;
            if(i==2*temp-1){
                index++;
                temp=(int)Math.pow(2,index);
            }
        }
        return res;
    }

    public int matrixScore(int[][] A)
    {
        int len=A.length;
        for(int i=0;i<len;i++){
            if(A[i][0]==0){
                for(int j=0;j<A[0].length;j++){
                    A[i][j]=(A[i][j]+1)%2;
                }
            }else {
                continue;
            }
        }
        for(int j=0;j<A[0].length;j++){
            int num=0;
            for(int i=0;i<len;i++){
                if(A[i][j]==0){
                    num++;
                }
            }
            if(num>len/2){
                for(int i=0;i<len;i++){
                    A[i][j]=(A[i][j]+1)%2;
                }
            }
        }
        int sum=0;
        for(int i=0;i<len;i++){
            int sumone=0;
            for(int j=0;j<A[0].length;j++){
                sumone=sumone*2+A[i][j];
            }
            sum+=sumone;
        }
        return sum;
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph)
    {
        List<List<Integer>> res=new ArrayList<>();
        int len=graph.length;
        int data[][]=new int[len][len];
        for(int i=0;i<len;i++){
            for(int j=0;j<graph[i].length;j++){
                data[i][graph[i][j]]=1;
            }
        }
        List<Integer> node=new ArrayList<>();
        node.add(0);
        allPossibleFBTOne(res,node,data,0);
        return res;
    }

    private void allPossibleFBTOne(List<List<Integer>> res, List<Integer> node, int[][] data, int i) {
        if(i==data.length-1){
            res.add(new ArrayList<>(node));
        }else {
            for(int j=0;j<data.length;j++){
                if(data[i][j]==1){
                    node.add(j);
                    allPossibleFBTOne(res,node,data,j);
                    node.remove(node.size()-1);
                }
            }
        }
    }

    public int singleNonDuplicate(int[] nums) {
        int len=nums.length;
        int num=0;
        for(int i=0;i<len;i++){
            num^=nums[i];
        }
        return num;
    }

    public int sumNumbers(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        int one=0;
        if(root==null){
            return 0;
        }
        sumNumbersOne(res,root,one);
        Iterator<Integer> integerIterator=res.iterator();
        int result=0;
        while (integerIterator.hasNext()){
            result+=integerIterator.next();
        }
        return result;
    }

    private void sumNumbersOne(List<Integer> res, TreeNode root, int one) {
        if(root.left==null&&root.right==null){
            one=one*10+root.val;
            res.add(one);
            one=(one-root.val)/10;
        }
        else {
            one=one*10+root.val;
            if(root.left!=null)
                sumNumbersOne(res,root.left,one);
            if(root.right!=null)
                sumNumbersOne(res,root.right,one);
            one=(one-root.val)/10;
        }
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1){
            return triangle.get(0).get(0);
        }else {
            List<Integer> node=triangle.get(0);
            List<Integer> temp;
            for(int i=1;i<triangle.size();i++){
                temp=triangle.get(i);
                temp.set(0,node.get(0)+temp.get(0));
                for(int j=1;j<temp.size()-1;j++){
                    int b=node.get(j-1),c=node.get(j);
                    b=b<c?b:c;
                    temp.set(j,b+temp.get(j));
                }
                temp.set(temp.size()-1,temp.get(temp.size()-1)+node.get(temp.size()-2));
                node=temp;
            }
            int min=Integer.MAX_VALUE;
            Iterator<Integer> integerIterator=node.iterator();
            while (integerIterator.hasNext()){
                int t=integerIterator.next();
                min=t<min?t:min;
            }
            return min;
        }
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        preorderTraversaldfs(root,res);
        return res;
    }

    private void preorderTraversaldfs(TreeNode root, List<Integer> res)
    {
        if(root==null){
            return;
        }
        res.add(root.val);
        preorderTraversaldfs(root.left,res);
        preorderTraversaldfs(root.right,res);
    }

    public boolean stoneGame(int[] piles)
    {
        return true;
    }

    public TreeNode pruneTree(TreeNode root) {
        if(root==null) return null;
        root.left=pruneTree(root.left);
        root.right=pruneTree(root.right);
        if(root.left==null&&root.right==null&&root.val==0)return null;
        return root;
    }

    public String complexNumberMultiply(String a, String b) {
        int index=a.indexOf("+");
        int a1=Integer.parseInt(a.substring(0,index));
        String s=a.substring(index+1,a.length()-1);
        int a2;
        if(s.equals("")){
            a2=1;
        }else if(s.equals("-")){
            a2=-1;
        }else {
            a2=Integer.parseInt(s);
        }
        index=b.indexOf("+");
        int b1=Integer.parseInt(b.substring(0,index));
        s=b.substring(index+1,b.length()-1);
        int b2;
        if(s.equals("")){
            b2=1;
        }else if(s.equals("-")){
            b2=-1;
        }else {
            b2=Integer.parseInt(s);
        }
        int c1=a1*b1-a2*b2;
        int c2=a1*b2+a2*b1;
            return c1+"+"+c2+"i";
    }

    public int countBattleships(char[][] board) {
        int len=board.length;
        if(len==0)return 0;
        else
        {
            int len2=board[0].length;
            int count=0;
            for(int i=0;i<len;i++)
            {
                for(int j=0;j<len2;j++)
                {
                    if(board[i][j]=='X'&&(i==0||board[i-1][j]=='.')&&(j==0||board[i][j-1]=='.'))
                    {
                        count++;
                    }
                }
            }
            return count;
        }
    }

    public String optimalDivision(int[] nums)
    {
        int len=nums.length;
        if(len==0) return "";
        else if (len==1)
        {
            return nums[0]+"";
        }
        else if(len==2)
        {
            return nums[0]+"/"+nums[1];
        }
        else
        {
            StringBuilder sb=new StringBuilder();
            sb.append(nums[0]);
            sb.append("/(");
            for(int i=1;i<len-1;i++){
                sb.append(nums[i]).append("/");
            }
            sb.append(nums[len-1]);
            sb.append(")");
            return sb.toString();
        }
    }

    public void gameOfLife(int[][] board)
    {
        int H=board.length,W=board[0].length;
        int [][]res=new int[H][W];
        for(int i=0;i<H;i++)
        {
            for(int j=0;j<W;j++)
            {
                int temp=calGameOfLife(board,i,j);
                if(temp<2)
                {
                    res[i][j]=0;
                }
                else if(temp==2)
                {
                    res[i][j]=board[i][j];
                }
                else if(temp==3)
                {
                    res[i][j]=1;
                }
                else
                {
                    res[i][j]=0;
                }
            }
        }
        board=res;
        int i=0;
    }

    private int calGameOfLife(int[][] board, int i, int j) {
        int count=0;
        if(i>0&&board[i-1][j]==1)
        {
            count++;
        }
        if(i>0&&j>0&&board[i-1][j-1]==1)
        {
            count++;
        }
        if(i>0&&j<board[0].length-1&&board[i-1][j+1]==1)
        {
            count++;
        }
        if(j>0&&board[i][j-1]==1)
        {
            count++;
        }
        if(j<board[0].length-1&&board[i][j+1]==1)
        {
            count++;
        }
        if(i<board.length-1&&board[i+1][j]==1)
        {
            count++;
        }
        if(i<board.length-1&&j>0&&board[i+1][j-1]==1)
        {
            count++;
        }
        if(i<board.length-1&&j<board[0].length-1&&board[i+1][j+1]==1)
        {
            count++;
        }
        return count;
    }

    public List<Integer> largestValues(TreeNode root)
    {
        Queue<TreeNode> queue=new LinkedList<>();
        List<Integer> res=new ArrayList<>();
        if(root==null)
        return res;
        queue.add(root);
        while (queue.size()!=0){
            int size=queue.size();
            int max=Integer.MIN_VALUE;
            for(int i=0;i<size;i++){
                TreeNode t=queue.poll();
                max=max>t.val?max:t.val;
                if(t.left!=null)
                    queue.add(t.left);
                if(t.right!=null)
                    queue.add(t.right);
            }
            res.add(max);
        }
        return res;
    }

    public int numberOfArithmeticSlices(int[] A)
    {
        int len=A.length;
        if(len<3) return 0;
        int sub[]=new int[len-1];
        for(int i=0;i<len-1;i++)
            sub[i]=A[i+1]-A[i];
        int i=0,j=i+1;
        int num=0;
        while (j<len-1)
        {
            if(sub[j]==sub[i])
            {
                j++;continue;
            }
            else
            {
                int temp=j-i-1;
                i=j;j++;
                for(int k=1;k<=temp;k++)
                {
                    num+=k;
                }
            }
        }
        int temp=j-i-1;
        i=j;j++;
        for(int k=1;k<=temp;k++)
        {
            num+=k;
        }
        return num;

    }

    public List<Integer> findDuplicates(int[] nums)
    {
        Arrays.sort(nums);
        List<Integer> res=new ArrayList<>();
        int i=0,len=nums.length;
        for(;i<len-1;i++)
        {
            int j=i+1;
            if(nums[j]==nums[i])
            {
                res.add(nums[j]);
                while (j<len&&nums[j]==nums[i])
                {
                    j++;
                }
                i=j-1;
            }
        }
        return res;
    }

    public int findDuplicate(int[] nums)
    {
        int len=nums.length;
        int []data=new int[len];
        for(int i=0;i<len;i++)
        {
            data[nums[i]]++;
        }
        for(int i=0;i<len;i++)
        {
            if(data[i]>=2)
            {
                return i;
            }
        }
        return -1;
    }

    public String customSortString(String S, String T)
    {
        char[]chars={'a','b','c','d','e','f','g','h','i','j','k','l','m',
                      'n','o','p','q','r','s','t','u','v','w','x','y','z'};
        int[]data=new int[26];
        int len=T.length();
        for(int i=0;i<len;i++)
        {
            data[T.charAt(i)-'a']++;
        }
        StringBuilder sb=new StringBuilder();
        len=S.length();
        for(int i=0;i<len;i++)
        {
            int num=data[S.charAt(i)-'a'];
            for(int j=0;j<num;j++)
            {
                sb.append(chars[S.charAt(i)-'a']);
            }
            data[S.charAt(i)-'a']=0;
        }
        for(int i=0;i<26;i++)
        {
            if(data[i]!=0)
            {
                int num=data[i];
                for(int j=0;j<num;j++)
                {
                    sb.append(chars[i]);
                }
            }
        }
        return sb.toString();
    }
}
